#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<unordered_set>
using namespace std;

class Solution{
    public:
    //my ans --out of time
    vector<int> ans1(string s, vector<string>& words){
        int str_length = s.size();
        int len = words[0].size();
        int word_num = words.size();
        int word_length = word_num * len;
        unordered_multiset<string> temp_word;
        unordered_multiset<string> word;
        vector<int> index;

        for(int i = 0; i != word_num; i++){
            word.insert(words[i]);
        }
        for(int i = 0; i != str_length - word_length + 1; i++){
            int flag = 0;
            string temp = s.substr(i, word_length);
            for(int j = 0; j != word_num; j++){
                temp_word.insert(temp.substr(j*len, len));
            }
            for(int j = 0; j != word_num; j++){
                string subword = temp.substr(j*len, len);
                if(word.count(subword) == temp_word.count(subword)){
                    flag++;
                }
            }
            for(int j = 0; j != word_num; j++){
                temp_word.erase(temp.substr(j*len, len));
            }
            if(word.size() == flag){
                index.push_back(i);
            }
        }

        return index;
    }

    vector<int> ans2(string s, vector<string>& words){
        vector<int> res;
        int m = words.size(), n = words[0].size(), ls = s.size();
        for (int i = 0; i < n && i + m * n <= ls; ++i) {
            unordered_map<string, int> differ;
            for (int j = 0; j < m; ++j) {
                ++differ[s.substr(i + j * n, n)];
            }
            for (string &word: words) {
                if (--differ[word] == 0) {
                    differ.erase(word);
                }
            }
            for (int start = i; start < ls - m * n + 1; start += n) {
                if (start != i) {
                    string word = s.substr(start + (m - 1) * n, n);
                    if (++differ[word] == 0) {
                        differ.erase(word);
                    }
                    word = s.substr(start - n, n);
                    if (--differ[word] == 0) {
                        differ.erase(word);
                    }
                }
                if (differ.empty()) {
                    res.emplace_back(start);
                }
            }
        }
        return res;
    }

};

void test1(){
    Solution s;
    string str = "barfoothefoobarman";
    vector<string> words = {"foo","bar"};
    // vector<int> ret = s.ans1(str, words);
    vector<int> ret = s.ans2(str, words);
    for(int i = 0; i != ret.size()-1; i++){
        cout << ret[i] << " " << ends;
    }
    cout << ret[ret.size()-1] << endl;
}

void test2(){
    Solution s;
    string str = "wordgoodgoodgoodbestword";
    vector<string> words = {"word","good","best","word"};
    // vector<int> ret = s.ans1(str, words);
    vector<int> ret = s.ans2(str, words);
    for(int i = 0; i != ret.size()-1; i++){
        cout << ret[i] << " " << ends;
    }
    cout << ret[ret.size()-1] << endl;
}

void test3(){
    Solution s;
    string str = "barfoofoobarthefoobarman";
    vector<string> words = {"bar","foo","the"};
    // vector<int> ret = s.ans1(str, words);
    vector<int> ret = s.ans2(str, words);
    for(int i = 0; i != ret.size()-1; i++){
        cout << ret[i] << " " << ends;
    }
    cout << ret[ret.size()-1] << endl;
}

int main(void){
    test1();
    // test2();
    test3();

    return 0;
}